package algorithm;

import java.util.Arrays;

public class TriangleNumber {
    public static void main(String[] args) {
           int[] nums = new int[]{4,2,3,4};
           System.out.println(triangleNumber(nums));
    }

    public static int triangleNumber(int[] nums) {
          //先排序
          Arrays.sort(nums);

          //设置一个计数器
          int count = 0;
          int tail = nums.length - 1;

          //首先固定最大的数
          while(tail >= 2) {
              //在最大数的左区间之内，使用双指针算法。快速统计出符合要求的三元组的个数
              int left = 0,right = tail - 1;
              while(left < right) {
                  if(nums[left] + nums[right] > nums[tail]) {
                      count += (right - left);
                      right--;
                  } else {
                      left++;
                  }
              }
              tail--;
          }
          return count;
    }
}
